Problem statement: zenit17kki

Ííha, ale je ten špagát dlhý!

Počet bodov: 35, časový limit: 900ms

Šandyna sa hrala so špagátmi. Zobrala prvý špagát, druhý špagát, od začiatku prvého špagátu namerala \(3\) centimetre, od začiatku druhého špagátu namerala \(6\) centimetrov a v týchto bodoch špagáty zauzlila. Ďalej zobrala tretí špagát a niekde ho zauzlila s druhým. Potom zobrala štvrtý špagát, …

Takto dostala dlhú šnúru špagátov. Bola až taká dlhá, že Šandyne napadla otázka: ``Ako najviac viem túto reťaz špagátov natiahnuť za niektoré konce? Teda: ako najďalej sú od seba tie dva konce šnúry, ktoré majú medzi sebou najviac špagátu?’’

Šnúra má ale veľa koncov, a skúšať všetky možnosti sa jej teda nechce. Zaznačila si ale o každom špagáte jeho dĺžku a v ktorých vzdialenostiach od začiatku sú na ňom uzly (kde sa napája na predchádzajúci a nasledujúci špagát). Ak budeme predpokladať, že na každý uzol sa nespotrebuje žiadna dĺžka špagátu, tak z vyššie uvedených informácií sa dá odpoveď na Šandyninu otázku ľahko vypočítať.

Vstup a výstup

Na prvom riadku vstupu dostanete počet testovacích prípadov \(t\). Nasledujú ich popisy.

Popis každého testu začína prázdnym riadkom, a potom riadkom s celým číslom \(n\) reprezentujúcim počet špagátov, pričom \(1 \leq n \leq 100\,000\).

Na nasledujúcich \(n\) riadkoch nasledujú Šandynine záznamy o špagátoch. \(i\)-ty riadok pozostáva z troch medzerou oddelených celých čísel \(d_i, p_i, n_i\): dĺžka špagátu, ako ďaleko od začiatku je uzol s predchádzajúcim špagátom, a ako ďaleko od začiatku je uzol s nasledujúcim špagátom. Platí \(1 \leq d_i \leq 10^{18}\) a \(-1 \leq p_i, n_i \leq d_i\), pričom \(p_i = -1\) iba pre prvý špagát, a \(n_i = -1\) iba pre posledný.

Na výstup vypíšte \(t\) riadkov, na \(i\)-tom z nich nech je jedno celé číslo: najväčšia dĺžka šnúry z \(i\)-teho testu. Môžete predpokladať, že správna odpoveď nikde nebude väčšia ako \(10^{18}\).

Príklad

Input:

1

3
2 -1 1
9 6 3
2 1 -1

Output:

9

Nie vždy sa oplatí začínať pri prvom špagáte a končiť pri poslednom. Takisto nemusí platiť \(p_i \leq n_i\).